Many different types of information transmission systems utilize error correction techniques to improve their efficiency. This is particularly true for those systems that need to reliably function across inherently noisy communications channels. Examples include wired systems for transmitting and receiving across noise prone physical communications lines (e.g., cable modems, DSL modems, and the like) and wireless systems for transmitting and receiving wirelessly via RF (e.g., wireless modems, wireless access points, wireless routers, and the like). Each of the above examples use an error correction system to improve efficiency.
An error correction system has the ability to both detect the presence of errors caused by noise or other impairments during transmission of data from a transmitter to a receiver, and the ability to reconstruct the original, error-free data. Generally, the system functions by the transmitter encoding the data with an error-correcting code (ECC) and sending the resulting coded message to the receiver. The receiver decodes what it receives into the data that was “most likely” transmitted by the transmitter. The codes are designed so that it would take an “unreasonable” amount of noise to trick the receiver into misinterpreting the data.
One of the more widely used ECC techniques is the low-density parity check code. A low-density parity-check code (LDPC code) is an error correcting code that increases the efficiency of transmitting data over a noisy channel. Although LDPC and other error correcting codes cannot guarantee perfect reconstruction of a transmitted signal, the probability of lost information can be made very small. LDPC was the first code to allow data transmission rates close to the theoretical maximum, and remains, one of the most effective ECC's developed to date. The explosive growth in information technology has produced a corresponding increase of commercial interest in the development of systems that implement the highly efficient LDPC codes. For example, an LDPC code system was selected to become the error correcting code in the new DVB-S2 standard for the satellite transmission of digital television.
The performance of an LDPC based transmission and reception system depends upon the performance of its LDPC encoder (e.g., within the transmitter) and its LDPC decoder (e.g., within the receiver). In particular, efficient overall system performance is more heavily affected by the performance of the LDPC decoder. As LDPC codes are being considered for use in a wide range of applications, the search for efficient implementations of decoding algorithms is being pursued intensively.
One of the more widely used LDPC decoding algorithms is the Belief Propagation algorithm. The belief propagation algorithm generally delivers good decoding performance. However, the belief propagation algorithm is problematic in that it can be computationally demanding. This property makes belief propagation algorithms difficult to efficiently implement in hardware. This has led to the development of a number of reduced-complexity variants of the BP algorithm that attempt to deliver satisfactory LDPC decoding performance while staying within a smaller power envelope (e.g., handheld devices, laptop computers, battery-powered components, etc.) or within a smaller hardware envelope (e.g., reduced cost, reduced transistor count, etc.).
Accordingly, a problem exists in that the numerous reduced-complexity variants of the BP algorithm involve compromises in their ability to deliver near-optimum decoding performance. For example, a low-power variant of the BP algorithm typically cannot provide enough throughput to satisfy more demanding applications. Similarly, a high-performance variant typically cannot be produced at a sufficiently low cost level to satisfy many mass-market applications.
Thus, there exists a great interest in the further optimization of BP algorithm LDPC decoder implementations.